/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86132
 * Date: 2022-03-16
 * Time: 12:35
 */
public class TestSort {


//最好情况下【每次都可以均匀分割待排序序列】时间复杂度：O(N*logN)
//空间复杂度：O(logN)  树的高度
//稳定性：不稳定

    //最坏情况下：数据有序，递归时变成单分支的树
    //最坏情况下【数据有序或数据逆序】时间按复杂度：O（N^2）数据有序一共有n个值，每次end都要从后往前走，走到start才能相遇，然后start在往后走一步，end再从后走到最前面
    //最坏情况下空间复杂度：O(N) 退化成了一棵单分支的树
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    public static void quick(int[] array,int left,int right){
        if(left>=right){//递归终止条件
            return;
        }
        //没有优化时候是用最左边的start位置的值放入tmp，然后根据tmp找基准
        //优化：三数取中法，找到三个数的中间大小的值，在用这个值与最左边的start位置值交换，再将最左边的start位置的值放入tmp，然后根据tmp找基准
        int midValIndex=findMidValIndex(array,left,right);//找到中间大小的下标
        swap(array,midValIndex,left);//将这个值与最左边的位置值交换，


        int pivot=partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int findMidValIndex(int[]array,int start,int end){
        int mid=start+((end-start)>>>1);//求中间位置mid，然后找start，mid，end的中间大小的值
        if(array[start]<array[end]){
            if(array[mid]<array[start]){
                return start;
            }else if(array[mid]>array[end]){
                return end;
            }else{
                return mid;
            }
        }else{//array[start]>array[end]
            if(array[mid]>array[start]){
                return start;
            }else if(array[mid]<array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }

    public static void swap(int[]array,int i,int j){//交换函数
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    private static int partition(int[]array,int start,int end){
        int tmp=array[start];
        while(start<end){
            while(start<end&&array[end]>=tmp){
                end--;
            }
            //此时end下标遇到了<tmp的值
            array[start]=array[end];
            while(start<end&&array[start]<=tmp){
                start++;
            }
            //此时start下标遇到了>tmp的值
            array[end]=array[start];
        }
        array[start]=tmp;//将tmp放入相遇位置
        return start;
    }
}
